#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;
//position in range
void count_sort(int unsort[],int sort[],int length,int k)
{
  int* range = (int*)malloc(k); //initializer fails to determine size of range

  //zero out range
  for(int i=0;i<k;i++)
    range[i] = 0;
  //set counter array range
  for(int i=0;i<length;++i) 
    range[unsort[i] ]++;
  //calculate its position
  for(int i=1;i<k;i++)
    range[i] +=range[i-1];
  //from length-1 downto 0 to keep it stable
  for(int i=length-1;i>=0;i--) {
    sort[range[unsort[i]]-1] = unsort[i];
    range[unsort[i]]--;
  }
}

int main()
{
  int unsort[10] = {3,4,3,1,2,6,5,2,8,0};
  int sort[10];
  count_sort(unsort,sort,10,9);

  copy(sort,sort+10,ostream_iterator<int>(cout," ") );
  cout<<endl;
  return 0;
}
  
  
